Ghi chú Chứng minh có thể kiểm chứng ngẫu nhiên (độ phức tạp)

↑ Sanjeev Arora, Shmuel Safra. “Probabilistic checking of proofs: A new characterization of NP”. Journal of the ACM, 45(1):70–122, 1998.

x t s Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được	DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP
Các lớp có thể không giải được	UP • NP (NP-đầy đủ · NP-khó · co-NP · co-NP-đầy đủ) • AM • PH • PP • #P (#P-đầy đủ) • IP • PSPACE (PSPACE-đầy đủ)
Các lớp được coi là không giải được	EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL
Các hệ thống cấp bậc	Cấp bậc đa thức • Cấp bậc hàm mũ • Cấp bậc Grzegorczyk • Cấp bậc số học
Các nhóm các lớp độ phức tạp	DTIME • NTIME • DSPACE • NSPACE • Chứng minh có thể kiểm chứng ngẫu nhiên • Hệ thống chứng minh tương tác

Liên quan

Tài liệu tham khảo